/**
 * MyViterbi.java created by zhangzhidong 
 * at 下午4:03:32 2015年10月25日
 */
package algorithm.viterbi;

/**
 * @author zhangzhidong
 *
 */
public class MyViterbi {
	/**
	 * Viterbi译码Java实现
	 * Viterbi算法方案简介：设给定词串W=w1 w2 … wk，Si(i=1,2…N)
	 * 表示词性状态（共有N种取值，其中N为词性符号的总数,可以通过语料库统计出来）,
	 * t=1,2…k表示词的序号（对应HMM中的时间变量），
	 * Viterbi 变量v(i,t)表示从w1的词性标记集合到wt的词性标记为Si的最佳路径概率值，
	 * 存在的递归关系是v(i,t)=max[v(i,t-1) * aij]*bj(wt),其中1≤t≤k, 1≤i≤N ,1≤j≤N,
	 * aij表示词性Si到词性Sj的转移概率,对应上述P(ti|ti-1) ，
	 * bj(wt)表示wt被标注为词性Sj的概率，即HMM中的发射概率，对应上述P(wi|ti)，
	 * 这两种概率值均可以由语料库计算。每次选择概率最大的路径往下搜索，
	 * 最后得到一个最大的概率值，再回溯，因此需要另一个变量用于记录到达Si的最大概率路径。
	 *	初始化参数：v(i,1)=p(i)* bi(w1)，p(i)表示经语料库统计计算得到该词性Si出现的频率，
	 *	即p(i)=Si出现的总次数/所有词性出现总次数N，bi(w1)表示词w1被标记为Si的概率，计算方式与前面相同。
	 * http://www.cnblogs.com/tornadomeet/archive/2012/03/24/2415889.html
	 * A矩阵就是delta矩阵
	 * 下午8:43:06 2015年10月25日
	 * @param observations 观测序列,也就是输入
	 * @param state	状态
	 * @param init	初始
	 * @param transitions 转移概率 
	 * @param emissions	发射概率 观察值与状态之间的关系
	 * @return A<br>
	 * 发送端发送的是-2 2 
	 * 有三条路径
	 *  状态有 0,(-2 -2) 1,(-2 2) 2,(2 -2) 3,(2 2) 
	 *  state = new int[]{0,1,2,3}
	 *  inti = new double[]{1,0,0,0}表示初始状态是 -2 -2;
	 * 
	 */
	public int [] viterbi(int observations[],int []states,double []init,double transitions[][],double emissions[][]){
		//0时刻对应A矩阵的第一列,状态对应行
		//A[i][j]表示的是长度为j-1的序列,变为i状态最大的概率
		double A[][] = new double[states.length][observations.length];
		int path[][]= new int[states.length][observations.length];
		//由初始状态计算A
		for(int i=0;i<init.length;i++){
			A[i][0]=init[i]*getMostLikely(i, getMapping(observations[0]), emissions);
		}
		for(int j =1 ;j<observations.length;j++){
			double max=0.0;
			double temp = 0.0;
//			v(i,t)=max[v(i,t-1) * aij]*bj(wt),其中1≤t≤k, 1≤i≤N ,1≤j≤N,
			for(int k=0;k<A.length;k++){
				//这个for循环,求最大的v(i,t-1) * aij
				for(int l=0;l<states.length;l++){
					temp = A[l][j-1]*transitions[l][k];
					if(max<temp){
						max=temp;
						path[k][j] = l;
					}
				}
				A[k][j] = max* getMostLikely(k, getMapping(observations[k]), emissions);
				if(temp>A[k][j]){
					A[k][j]=temp;
				}
			}
			
		}
		return null;
	}
	private double getMostLikely(int states,int whichOutput,double[][] mat){
		return mat[states][whichOutput];
	}
	private int getMapping(int k){
		return k==-2?0:1;
	}

	public static void main(String args[]){
		int []observations = new int[]{-2,2,2,2,2,2,-2,2};//接收到的序列
		int []states = new int []{0,1,2,3};
		double []init = new double[]{0.50,0.20,0.20,0.10};
		//以一种状态转移成为另外一种状态的概率
		double transitions[][] = new double[][] {{0,1,0,0},{0,0.2,0.5,0.3},{0,0,0.4,0.6},{1,0,0,0}};
		//在一种状态下可能产生的输出,这里0代表-2,1代表+2
		double emissions[][] = new double [][]{{0.55,0.45},{0.75,0.25},{0.95,0.05},{0.2,0.8}};
		new MyViterbi().viterbi(observations, states, init, transitions, emissions);
	}
//	private int getStatesMapping(int prior,int post){
//	if(prior==-2 && post ==-2 )return 0;
//	else if(prior==-2 && post==2)return 1;
//	else if(prior==2 && post ==-2) return 2;
//	else return 3;
//}
//private int get(int state,int obs){
//	return 0;
//}
}
